package 单周赛.history;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *
 */
public class 第304场单周赛 {

    public static void main(String[] args) {

        int[] nums = {1, 5, 0, 3, 5};
        System.out.println(minimumOperations(nums));

        int[] grades = {47, 2, 16, 17, 41, 4, 38, 23, 47};
        System.out.println(maximumGroups(grades));

    }

    public static int minimumOperations(int[] nums) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>
                (nums.length, (o1, o2) -> (o1 - o2));
        for (int num : nums) {
            if (num != 0) {
                priorityQueue.add(num);
            }
        }
        int count = 0;
        while (!priorityQueue.isEmpty()) {
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> (o1 - o2));
            Integer min = priorityQueue.poll();
            while (!priorityQueue.isEmpty()) {
                Integer cur = priorityQueue.poll();
                if ((cur - min) != 0) {
                    queue.add(cur - min);
                }
            }

            priorityQueue = queue;
            count++;
        }
        return count;
    }

    /**
     * 6133. 分组的最大数量 显示英文描述
     * 给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：
     * <p>
     * 第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
     * 第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。
     * 返回可以形成的 最大 组数。
     * <p>
     * 排序+贪心
     * 优先选择数字较小排序在前面
     *
     * @param grades
     * @return
     */
    public static int maximumGroups(int[] grades) {
        // 必须先排序
        Arrays.sort(grades);
        int ans = 1, preSum = grades[0], preCount = 1;
        int index = 1;
        while (index < grades.length) {
            int curSum = 0, curCount = 0;
            while (curSum <= preSum || curCount <= preCount) {
                curSum += grades[index];
                curCount++;
                index++;
                if (index == grades.length) break;
            }
            // 最后一组可能满足不了，并入倒数第二组
            if (curSum <= preSum || curCount <= preCount) return ans;
            preSum = curSum;
            preCount = curCount;
            ans++;
        }
        return ans;
    }

}
